# -*- coding: utf-8 -*-
# 直接插入排序

def insert_sort(array):
    n = len(array)
    for i in range(1, n):
        if array[i] < array[i - 1]:
            temp = array[i]
            index = i  # 待插入的下标
            for j in range(i - 1, -1, -1):  # 从i-1 循环到 0 (包括0)
                if array[j] > temp:
                    array[j + 1] = array[j]
                    index = j  # 记录待插入下标
                else:
                    break
            array[index] = temp
    return array
